package 算法.其他算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 把只包含质因子2、3和5的数称作丑数
 * 求按从小到大的顺序的第 n个丑数。
 */
public class JZ49丑数 {
    //最小堆
    //如果x是丑数，2x、3x、5x都是丑数
    public int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0;
        //要乘的因数
        int[] factors = {2, 3, 5};
        //去重
        HashMap<Long, Integer> mp = new HashMap<>();
        //小顶堆
        PriorityQueue<Long> pq = new PriorityQueue<>();
        //1先进去
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){
            //每次取最小的
            res = pq.poll();
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = (long)res * factors[j];
                //只取未出现过的
                if(!mp.containsKey(next)){
                    mp.put(next, 1);
                    pq.offer(next);
                }
            }
        }
        return (int) res;
    }


    //动态规划
    public int GetUglyNumber_Solution2(int index) {
        //排除0
        if(index == 0)
            return 0;
        //按顺序记录丑数
        ArrayList<Integer> num = new ArrayList<>();
        num.add(1);
        //记录这是第几个丑数
        int count = 1;
        //分别代表要乘上2 3 5的下标
        int i = 0, j = 0, k = 0;
        while(count < index){
            //找到三个数中最小的丑数
            num.add(findMin(num.get(i)*2,num.get(j)*3,num.get(k)*5));
            count++;
            //由2与已知丑数相乘得到的丑数，那该下标及之前的在2这里都用不上了
            if(num.get(count - 1) == num.get(i) * 2)
                i++;
            //由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if(num.get(count - 1) == num.get(j) * 3)
                j++;
            //由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
            if(num.get(count - 1) == num.get(k) * 5)
                k++;
        }
        return num.get(index-1);
    }

    int findMin(int x, int y, int z){
        int tmp = Math.min(x,y);
        int min = Math.min(tmp,z);
        return  min;
    }

}
